News Canada

Fri, July 20, 2007

Taking the fun out of checkers

EDMONTON -- It's taken dozens of computers humming away for almost 18 years, but a University of Alberta team has finally solved every possible game of checkers and concluded that as long as no mistakes are made, the game will end in a draw.

The popular game may be simple to play, but it holds a potential 500 billion billion positions. That's one million times more complicated than any other game solved before, says Jonathan Schaeffer, the computer science professor who began the project in 1989.

"In hindsight, it was ludicrous. Why tackle something a million times bigger?" said the wiry-haired academic. "Maybe there's a little bit of craziness there."

The team did trim down the number of positions examined. If a move in a certain position would lead to a win, the computer wouldn't look at other possible moves from that position that may lead to a draw or loss.

Schaeffer's proof was to be published in the academic journal Science yesterday. Schaeffer says that while the discovery is exciting from a computer science perspective, it shouldn't change how humans play the game.

More Newspaper Article on Friday and links:  Posted by Richard Beckwith on USAcheckers.com forum

 Here are some on-line article links. (Thanks to Pal Bucker for many of these.) I also spoke with LA Times, NY Times, Chicago Tribune, and COSMOS (Australian Magazine). I have a few more thoughts in Player's Rep Corner.

http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf
 

http://abcnews.go.com/Technology/story?id=3394382&page=1

http://discovermagazine.com/2007/jul/the-next-jump-in-artificial-intelligence

http://sciam.com/article.cfm?articleID=DBE35D70-E7F2-99DF-3ECB392CEF7AC028&chanID=sa003&ec=ab266_0719

The New York times
http://thelede.blogs.nytimes.com/2007/07/19/is-the-only-winning-move-not-to-play/

The Los Angeles Times
http://www.latimes.com/news/science/la-sci-checkers20jul20,0,884306.story?coll=la-home-center

Chicago Tribune
http://www.chicagotribune.com/news/local/chi-web_checkers_1_p.m.jul20,1,3313891.story?coll=chi-news-hed&ctrack=1&cset=true

Spectrum Online
http://www.spectrum.ieee.org/jul07/5379

Canadian Broadcast Corporation
http://www.cbc.ca/cp/Oddities/070719/K071925AU.html

The National Post (Canada)
http://communities.canada.com/nationalpost/blogs/posted/archive/2007/07/19/checkers-when-played-correctly-nobody-wins.aspx

Examiner.com
http://www.examiner.com/a-836720~Computer_Program_Can_t_Lose_at_Checkers.html
_________________
Richard Beckwith
ACF Player Rep

Articles